/////////////////////////////////////////////////////////////////////////////////////
/************************************************************************************

qdd: A Quantum Computer C++ Library constructed using BDD's

Copyright (C) 1999-2007 David Greve <TheBeaNerd@gmail.com>

This library is free software; you can redistribute it and/or modify
it under the terms of the GNU Library General Public License as
published by the Free Software Foundation; either version 2 of the
License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Library General Public License for more details.

You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
USA.

************************************************************************************/
/////////////////////////////////////////////////////////////////////////////////////

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <bdd.h>
#include <math.h>
#include "IntegerZ.h"
using namespace std;

#ifdef  QDD_DEBUG
#define QDD_ECHO(x) x
#else
#define QDD_ECHO(x) // x
#endif

/////////////////////////////////////////////////////////////////////////////////////
/************************************************************************************

  Support functions

************************************************************************************/
/////////////////////////////////////////////////////////////////////////////////////

extern int chose (void) ;

extern int BIT (const Integer &, unsigned int) ;

extern Integer rand (int) ;

extern Integer bitpown (const Integer &, unsigned int, const Integer &) ;

extern Integer powmod  (const Integer &, const Integer &, const Integer &) ;

extern Integer gcdm2 (const Integer &, const Integer &) ; 

extern Integer gcdm1 (const Integer &, const Integer &) ;

extern Integer pmod (const Integer &, const Integer &) ;

extern Integer invmod (const Integer &, const Integer &) ;

extern void qdd_error(const char *) ;

extern void qdd_assert (int, char *) ;

extern int ilog2 (Integer &) ;

extern int ilog2 (int) ;

extern bdd Int2IndexBDD (int index, int max_qbit) ;

extern bdd dag_satisfy(const bdd &, const bdd &) ;

/////////////////////////////////////////////////////////////////////////////////////
/************************************************************************************

  class::QuantumException

************************************************************************************/
/////////////////////////////////////////////////////////////////////////////////////

class QuantumException {

public:

  QuantumException(const char *);

  const char *msg;

};

/////////////////////////////////////////////////////////////////////////////////////
/************************************************************************************

  class::QuantumCondition									     

************************************************************************************/
/////////////////////////////////////////////////////////////////////////////////////

class QuantumBit;

class QuantumCondition {

  friend class QuantumBit;

  friend void qdd_regression();

private:

  bdd Value;
  bdd CumulativeIndex;

  QuantumCondition();

public:

  // QuantumCondition(const QuantumBit &);
  QuantumCondition & operator  & (const QuantumBit &);
  QuantumCondition & operator  & (QuantumCondition &);

};

/////////////////////////////////////////////////////////////////////////////////////
/************************************************************************************

  class:QuantumBit

************************************************************************************/
/////////////////////////////////////////////////////////////////////////////////////

class QuantumBit {

  friend class QuantumCondition;
  friend class QuantumRegister;

  friend void qdd_regression();
  friend void qdd_init(int maxbits, int maxram);

private:

  // QBit allocation mechanism

  static int *IndexHeap;
  static int  NextFreeIndex;

  // Each QuantumBit carries around a QuantumCondition for use in
  // conditional expressions.  When not in use, the value and
  // cumulative index of the Condition should be bddfalse.

  QuantumCondition Condition;

  // The Var (variable) associated with a quantum bit determines its
  // probability of being true or false.  With only one bit, we only
  // allow +/- 45 degree rotations (50% chance of being true/false).
  // In the future, this might be extended to more than one bit.
  // However, in general, even with an arbitrary number of bits, the
  // probability is still limited to some fraction of a power of 2.
  // Note that this approximation of quantum state is very weak .. so
  // weak, in fact, that algorithms relying on properties of Mix()
  // other than the fact that it places a single QBit in a
  // superposition of states will likely fail.  The primary limitation
  // of this technique is that it associates a given rotation with a
  // particular quantum bit.  For this reason, the use of Mix() is
  // restricted by the library.  Our guess is that most (all?)
  // digital quantum algorithms will be able to live with this
  // restriction .. but we may very well be wrong.

  bdd Var;

  // The location of a given QBit in the universe is determined by its
  // IndexBDD.  Simplifying the State of the Universe with the
  // IndexBDD of a QBit reveals the value of that QBit.  The IndexBDD
  // is (currently) quite simply the BDD representation of the natural
  // number value of the VAR number associated with the QBit.

  int Index;
  bdd IndexBDD;

  // Each Quantum bit "knows" about the State of the whole
  // QuantumUniverse.  The state is a bdd which can be simplified with
  // respect to a given IndexBDD to reveal the value of the quantum
  // bit associated with that IndexBDD.  Updating the value of a
  // single quantum bit, in some sense, updates the entire state.
  // Classical sampling of a quantum bit, in a real sense, collapses
  // the state in a way consistent with the value read from that
  // quantum bit.

  static bdd State;

  // bookkeeping 

  static int  INITIALIZED;
  static int  MIN_USER_QBIT;
  static int  MAX_QBITS;

  // Convenient shorthand for extracting and updating quantum bit
  // values.

  bdd Value() const;
  void putValue(bdd);

  // For now, these operations are illegal (protected and
  // unimplemented).  This is because they would likely lead to
  // inconsistent quantum states otherwise.

  QuantumBit(QuantumBit &); 				// Copying
  QuantumBit & operator = (const QuantumBit &);		// Assignment

  void QuantumBitInit(int);

public:

   QuantumBit(int);
   QuantumBit();
  ~QuantumBit();

  void unMixed();
  void Mix();
  int  Sample();
  void Set(int);

  void               operator  ~     ();
  QuantumCondition & operator  !     ();
  void               operator ^=     (      QuantumCondition &);
  void               operator ^=     (const QuantumBit &);
  QuantumCondition & operator  &     (const QuantumBit &);
  QuantumCondition & operator  &     (      QuantumCondition &);

};

/////////////////////////////////////////////////////////////////////////////////////
/************************************************************************************

  class:QuantumRegister

************************************************************************************/
/////////////////////////////////////////////////////////////////////////////////////

class QuantumRegister {

  friend void qdd_regression();

private:

  QuantumBit * QuBit;

  // For now, these operations are illegal ...

  QuantumRegister(QuantumRegister &); 				// Copying
  QuantumRegister & operator = (const QuantumRegister &);	// Assignment

public:

  int  Size;

  QuantumRegister(int) ;
  ~QuantumRegister() ;

  QuantumBit & operator [] (int index);  

  void         unMixed();
  void         Mix();
  Integer      Sample();
  void         Set(const Integer &);
  Integer      Period();

  void         operator ^= (const QuantumRegister &);

};
